Color in documents is the result of a combination of a limited set of colors over a small area, in densities selected to integrate to a desired color response. This is accomplished in many printing devices by reproducing separations of the image, where each separation provides varying density of a single primary color. When combined together with other separations, the result is a full color image.
In the digital reproduction of documents, a separation is conveniently represented as a monochromatic bitmap, which may be described as an electronic image with discrete signals (hereinafter, pixels) defined by position and density. In such a system, density is described as one level in a number of possible states or levels. When more than two levels of density are used in the description of the image, the levels are often termed "gray", indicating that they vary between a maximum and minimum, and without reference to their actual color. Most printing systems have the ability to reproduce an image with a small number of levels, most commonly two, although other numbers are possible. Common input devices including document scanners, digital cameras and the computer imagery generators, however, are capable of describing an image with a substantially larger number of gray levels, with 256 levels a commonly selected number, although larger and smaller levels are possible. It is required that an image initially described at a large set of levels also be describable at a smaller set of levels, in a manner which captures the intent of the user. In digital reproduction of color documents this means that each of the color separations is reduced from the input number of levels to a smaller output number of levels. The multiple color separations are combined together at printing to yield the final color print. Commonly, color documents are formed using cyan, magenta and yellow colorants or cyan, magenta, yellow and black colorants. A larger number or alternative colorants may also be used.
In printing documents, the desired density of color over an area is commonly achieved by halftoning, where separation density variation is represented by placing greater or less numbers of ON pixels in a discrete area of a separation. In one halftoning method known as dithering or screening, over a given area having a number of gray separation pixels therein, a value representing the density of each separation pixel of an array of gray separation pixels within the area is compared to one of a set of preselected thresholds (the thresholds are stored as a dither matrix and the repetitive pattern generated by this matrix is considered a halftone cell) as taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is gray, some of the thresholds within the dither matrix will be exceeded, i.e. the image value at that specific location is larger than the value stored in the dither matrix for that same location, while others are not. In the binary case, the separation pixels or cell elements for which the thresholds are exceeded might be printed as a maximum colorant value, while the remaining separation pixels are allowed to remain white, dependent on the actual physical quantity described by the data. The described halftoning method produces an output pattern that is periodic or quasi-periodic in the spatial coordinates.
Dithering creates problems in color document reproduction where the repeating pattern of a screen through the image, when superposed over similar repeating patterns in multiple separations, can cause moire or other artifacts, particularly in printing systems with less than ideal registration between separations. The artifacts caused by mis-registration can be understood from simple examples.
Assuming for simplicity two separations having halftone screens having identical screen frequencies and angles. Printing those two separations on top one another in perfect registration will give a homogeneous color without periodic artifacts. If the second screen is spatially shifted with respect to the first screen, a strong shift in the output color will occur. Printing systems that are likely to have such a spatial displacement between the separations due to physical limitations are prone to color shift artifacts in the final prints. A different type of artifact occurs if the printing system is likely to have a slight rotation between separations. In these instances, a color moire is formed spatially progressing from one color to another.
In another example, assuming again for simplicity two separations having halftone screens having identical screen frequencies but different angles. Printing those two separations on top one another in perfect registration will give a homogeneous color and, depending on the angle between the two separations, a high or low frequency moire. In situations where the angle is large (e.g.: 30.degree.) a high frequency moire occurs which is usually not distracting, and in cases where the angle is small (e.g.: 2.degree.) a low frequency moire occurs which is usually distracting. If these two separations are printed shifted with respect to one another, no color shift is perceived in constant color areas, and no change in the moire frequency occurs. A halftone screen scheme using different angles for the different color separations is therefore less sensitive to a spatial displacement than a scheme using identical angles for all separations. If the two separations are printed with a change in the angle between the separations, the frequency and direction of the moire is altered and a non-objectionable moire might be changed to an objectionable moire.
There are always 2-way moire patterns between the color separations, but the angles are chosen to maximize the frequency of the moires (they are about 1/2 the screen frequency). These are the "rosettes" noted in magnified color halftones. This is true of both analog (photographic) and digital systems and is not a significant quality problem. Whenever a fourth color (black or "key") is included, there is another moire pattern, formed by a 3-way interaction between cyan, magenta and black. In analog systems, this is at zero frequency. In digital systems which use the Holladay rational angle screens, or the like angles of exactly 15 degrees are not possible, so the 3-way moire is not quite at zero frequency, but is at a very objectionable low frequency.
The color halftoning scheme using different angles for some or all of the color separations is common for applications that have slight mis-registrations due to physical limitations. Accordingly, and with reference again to U.S. Pat. No. 4,194,194 to Holladay, the angle of the screen can be changed to generate similar screen patterns which do not strongly beat visually against each other, with the result the objectionable moire is reduced. Particularly critical are the angles between the most prominent colors, particularly cyan, magenta and black (if present). A common arrangement of rotated screen angles is 0.degree., 15.degree., 45.degree. and 75.degree. for yellow, cyan, black and magenta, respectively, in which case all separations are commonly halftoned using the same screen frequency, sometimes with the exception of yellow. However, objectionable patternings still can occur.
The above described halftoning processes generate periodic halftone patterns. Other methods exist that generate non-periodic or quasi non-periodic structure. Examples for such methods are error diffusion and similar halftoning processes, stochastic screening and pulse density modulation.
Error diffusion, is taught, in "An Adaptive Algorithm for Spatial Greyscale" by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77 (1976) (hereinafter, "Floyd and Steinberg"). Another, more elaborate method would be the error diffusion techniques of U.S. Pat. No. 5,045,952 to Eschbach, which serves to provide image dependent edge enhancement, assigned to the same assignee as the present invention. Error diffusion attempts to maintain gray by making the conversion from gray pixels to binary or other level pixels on a pixel-by-pixel basis. The procedure examines each pixel with respect to a threshold, and the difference between the gray level pixel value and the output value is forwarded to a selected group or set of neighboring pixels, in accordance with a weighting scheme. The output binary pattern of the error diffusion algorithm and its derivatives is a pattern with a local periodicity related to the input density level, but with no global periodicity, see "Analytic Description of the 1-D Error Diffusion Technique for Halftoning," Optics Communications, Vol. 52, No. 3, 165-168 (1984) by R. Eschbach and R. Hauck.
Other error diffusion methods include, "On the Error Diffusion Technique for Electronic Halftoning" by Billotet-Hoffmann and Bryngdahl, Proceedings of the SID, Vol. 24/3, (1983), pp. 253-258; and U.S. Pat. No. 5,226,094 to Eschbach. A technique related to error diffusion is taught in the MAE (Minimum Average Error) method of error diffusion described in "Images from Computers", by M. Schroeder, IEEE Spectrum, March 1969, pp. 66-78, in which an error correction is performed that only affects a local neighborhood. This method does not preserve the gray density. One particularly effective error diffusion variant is taught in co-pending U.S. patent application No. 08/167,758, filed Dec. 15, 1993, entitled "Method for Quantization Gray Level Pixel Data with Extended Distribution Set", by J. Shiau and Z. Fan.
Error diffusion, because it operates on a pixel-by-pixel basis is non-periodic, which mitigates the problems of moire. However, since error diffusion is a deterministic process, misregistration of the different deterministic color separations can lead to a color shift. This color shift can be reduced by introducing a random element into the error diffusion process, but at the expense of image noise.
Stochastic screening (of which error diffusion might be considered one type) describes other ways to generate a non-periodic output pattern. U.S. Pat. No. 4,485,397 to Scheuter et al. describes a method for generating a non-periodic halftone distribution by determining areas of constant or nearly constant input density and by distributing a precalculated number of print dots inside each area based on a random or pseudo random number and some spatial constraints.
U.S. Pat. No. 4,876,611 to Fischer et al. describes another stochastic screening algorithm in which the print/no-print decision is based on a recursive subdivision of the print field maintaining average density over the larger print field.
A non-periodic halftoning scheme based on a pulse-density modulation is taught in "Binarization using a two-dimensional pulse-density modulation", by R. Eschbach and R. Hauck, Journal of the Optical Society of America A, 4, 1873-1878 (1987) and "Pulse-density modulation on rastered media: combining pulse-density modulation and error diffusion", by R. Eschbach, Journal of the Optical Society of America A, 7, 708-716 (1990). In pulse-density modulation a mathematical model is used that guarantees the local density of print pulses as a function of the input image data.
One of the advantages of stochastic, non-periodic screening over periodic screening is the suppression of moire. However, mis-registration usually causes color shifts in stochastic screens, since the stochastic screens are largely deterministic. The color shifts can be reduced by introducing randomness into the screening process, but this reduces the overall print quality by introducing visually non-pleasing noise.
In general it can be said that periodic halftone schemes suffer from a combination of color moire and color shifts on mis-registration, dependent on the actual scheme; that deterministic non-periodic halftone schemes suffer from color shifts on mis-registration; and that non-periodic random schemes suffer from image noise.
In U.S. Pat. No. 5,278,670 to Eschbach, a method of resolution conversion was described which suggested that the quantization step required could select either dithering or error diffusion, the selection based on a metric related to document content. The decision made applies to all the image separations describing an area.
U.S. Pat. No. 5,223,953 to Williams teaches an alternative hardware implementation of Holladay.
U.S. Pat. No. 5,225,915 to Ciccone et al. illustrates that the addition of noise or enhancement of inherent noise can mask the structure moire. However, such schemes inherently alter the accuracy of the image.
U.S. patent application No. 07/922,421, filed Jul. 31, 1992, entitled "High Addressability Error Diffusion with Minimum Mark Size", by R. Eschbach, provides a discussion on the implementation of error diffusion in a high addressability printing system, while maintaining a minimum mark size. This reference is incorporated by reference for its teachings.
All of the references cited herein are incorporated by reference for their teachings.